package _17_剑指Offer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class _38_剑指Offer字符串的排列 {

    public static void main(String[] args) {

        _38_剑指Offer字符串的排列 v = new _38_剑指Offer字符串的排列();


        System.out.println(Arrays.toString(v.permutation("aab")));

    }

    private final List<String> results = new ArrayList<>();

    public String[] permutation(String s) {
        char[] chars = s.toCharArray();

        dfs(chars, 0);
        return results.toArray(new String[0]);
    }

    private void dfs(char[] chars, int i) {
        if (i == chars.length) {
            results.add(new String(chars));
        }
        for (int j = i; j < chars.length; j++) {
            // 看前面是否存在相同的值
            if (!isRepeat(chars, i, j)) {
                swap(chars, i, j);
                dfs(chars, i + 1);
                swap(chars, i, j);
            }
        }
    }

    private boolean isRepeat(char[] chars, int i, int j) {
        int cur = chars[j];
        for (int k = i; k < j; k++) {
            if (cur == chars[k]) return true;
        }
        return false;
    }

    private void swap(char[] chars, int index1, int index2) {
        char temp = chars[index1];
        chars[index1] = chars[index2];
        chars[index2] = temp;
    }

}
